{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count and Say"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countAndSay"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #外观数列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>n</code> ，输出外观数列的第 <code>n</code> 项。</p>\n",
    "\n",
    "<p>「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。</p>\n",
    "\n",
    "<p>你可以将其视作是由递归公式定义的数字字符串序列：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>countAndSay(1) = \"1\"</code></li>\n",
    "\t<li><code>countAndSay(n)</code> 是对 <code>countAndSay(n-1)</code> 的描述，然后转换成另一个数字字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>前五项如下：</p>\n",
    "\n",
    "<pre>\n",
    "1.     1\n",
    "2.     11\n",
    "3.     21\n",
    "4.     1211\n",
    "5.     111221\n",
    "第一项是数字 1 \n",
    "描述前一项，这个数是 <code>1</code> 即 “ 一 个 1 ”，记作 <code>\"11\"\n",
    "</code>描述前一项，这个数是 <code>11</code> 即 “ 二 个 1 ” ，记作 <code>\"21\"\n",
    "</code>描述前一项，这个数是 <code>21</code> 即 “ 一 个 2 + 一 个 1 ” ，记作 \"<code>1211\"\n",
    "</code>描述前一项，这个数是 <code>1211</code> 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 \"<code>111221\"</code>\n",
    "</pre>\n",
    "\n",
    "<p>要 <strong>描述</strong> 一个数字字符串，首先要将字符串分割为 <strong>最小</strong> 数量的组，每个组都由连续的最多 <strong>相同字符</strong> 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。</p>\n",
    "\n",
    "<p>例如，数字字符串 <code>\"3322251\"</code> 的描述如下图：</p>\n",
    "<img alt=\"\" src=\"https://pic.leetcode-cn.com/1629874763-TGmKUh-image.png\" style=\"width: 581px; height: 172px;\" />\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>\"1\"\n",
    "<strong>解释：</strong>这是一个基本样例。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>\"1211\"\n",
    "<strong>解释：</strong>\n",
    "countAndSay(1) = \"1\"\n",
    "countAndSay(2) = 读 \"1\" = 一 个 1 = \"11\"\n",
    "countAndSay(3) = 读 \"11\" = 二 个 1 = \"21\"\n",
    "countAndSay(4) = 读 \"21\" = 一 个 2 + 一 个 1 = \"12\" + \"11\" = \"1211\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 30</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-and-say](https://leetcode.cn/problems/count-and-say/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-and-say](https://leetcode.cn/problems/count-and-say/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        result = '1' # '21'\n",
    "        for i in range(2,n+1): # i=4\n",
    "            newResult = [] # ['12','11']\n",
    "            currentDigit = result[0] # '1'\n",
    "            digitCount = 0 # 1\n",
    "            for digit in result: # digit='1'\n",
    "                if currentDigit == digit: \n",
    "                    digitCount += 1\n",
    "                else:\n",
    "                    newResult.append(str(digitCount) + currentDigit)\n",
    "                    currentDigit = digit\n",
    "                    digitCount = 1\n",
    "            newResult.append(str(digitCount) + currentDigit)\n",
    "            result = ''.join(newResult)\n",
    "        return(result)\n",
    "        \n",
    "\n",
    "# Test Cases: \n",
    "# 1 -> \"1\"\n",
    "# 2 -> \"11\"\n",
    "# 3 -> \"21\"\n",
    "# 4 -> \"1211\"\n",
    "# 5 -> \"111221\"\n",
    "# 6 -> \"312211\"\n",
    "# 6 -> \"13112221\"\n",
    "# \n",
    "#               time        space\n",
    "# Approach 1:   O(n^2)      O(n) - O(exp(n)) probably closer to O(n)\n",
    "# \"Recurson approach\"\n",
    "# Base case: if 1 -> \"1\"\n",
    "# otherwide comput n-1 case\n",
    "# Define current digit\n",
    "# Define digitCounter\n",
    "# Iterate through n-1 result, \n",
    "# Increment digit counter, every time encouter new digit, add to result string\n",
    "#\n",
    "# Approach 2:   O(n^2)     O(1) - O(exp(n)), probably closer to O(n) \n",
    "# Create base case\n",
    "# Iterate upwards in n\n",
    "# Loop through with currentDigit and digitCounter\n",
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        p = self.countAndSay(n - 1)\n",
    "        res = \"\"\n",
    "        t = p[0]\n",
    "        count = 1\n",
    "        for i in range(1, len(p)):\n",
    "            if p[i] == p[i - 1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                res = res + str(count)\n",
    "                res = res + t\n",
    "                t = p[i]\n",
    "                count = 1\n",
    "        res = res + str(count)\n",
    "        res = res + t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: 'int') -> 'str':\n",
    "        \n",
    "        def stringtosay(s):\n",
    "            last = None\n",
    "            count = 0\n",
    "            ret = ''\n",
    "            for c in s:\n",
    "                if c == last:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    if last:\n",
    "                        ret += str(count) + str(last)\n",
    "                    last = c\n",
    "                    count = 1\n",
    "            if last:\n",
    "                ret += str(count) + str(last)\n",
    "            return ret\n",
    "                \n",
    "        s = '1'\n",
    "        for i in range(n - 1):\n",
    "            s = stringtosay(s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        say = '1'\n",
    "        for i in range(0,n - 1):\n",
    "            next = ''\n",
    "            for item in [list(g) for k, g in itertools.groupby(say)]:\n",
    "                next += str(len(item)) + str(item[0])\n",
    "            say = next\n",
    "            print(say)\n",
    "        return say"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        s = '1'\n",
    "        for _ in range(n - 1):\n",
    "            s = ''.join(str(len(list(group))) + digit\n",
    "                        for digit, group in itertools.groupby(s))\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        dic = {1:\"1\",\n",
    "\t\t2:\"11\",\n",
    "\t\t3:\"21\",\n",
    "\t\t4:\"1211\",\n",
    "\t\t5:\"111221\",\n",
    "\t\t6:\"312211\",\n",
    "\t\t7:\"13112221\",\n",
    "\t\t8:\"1113213211\",\n",
    "\t\t9:\"31131211131221\",\n",
    "\t\t10:\"13211311123113112211\",\n",
    "\t\t11:\"11131221133112132113212221\",\n",
    "\t\t12:\"3113112221232112111312211312113211\",\n",
    "\t\t13:\"1321132132111213122112311311222113111221131221\",\n",
    "\t\t14:\"11131221131211131231121113112221121321132132211331222113112211\",\n",
    "\t\t15:\"311311222113111231131112132112311321322112111312211312111322212311322113212221\",\n",
    "\t\t16:\"132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211\",\n",
    "\t\t17:\"11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221\",\n",
    "\t\t18:\"31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211\",\n",
    "\t\t19:\"1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221\",\n",
    "\t\t20:\"11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211\",\n",
    "\t\t21:\"311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221\",\n",
    "\t\t22:\"132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211\",\n",
    "\t\t23:\"111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221\",\n",
    "\t\t24:\"3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211\",\n",
    "\t\t25:\"132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221\",\n",
    "\t\t26:\"1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211\",\n",
    "\t\t27:\"31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221\",\n",
    "\t\t28:\"13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211\",\n",
    "\t\t29:\"11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221\",\n",
    "\t\t30:\"3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211\"}\n",
    "        return dic[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        s = \"1\"\n",
    "        count = 0\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            k = 0\n",
    "            tmp = \"\"\n",
    "            l = len(s)\n",
    "            j = 0\n",
    "            a = s[j]\n",
    "            while j < l:\n",
    "                if a == s[j]:\n",
    "                    count += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    tmp += (str(count) + a)\n",
    "                    count = 0\n",
    "                    a = s[j]\n",
    "            s = tmp + str(count) + a\n",
    "            i += 1\n",
    "            count = 0\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if n == 0:\n",
    "            return \"\"\n",
    "        cur = \"1\"\n",
    "        for k in range(1, n):\n",
    "            prev = cur\n",
    "            cur = \"\"\n",
    "            i = 0\n",
    "            for j in range(1, len(prev)):\n",
    "                if prev[j] != prev[i]:\n",
    "                    cur += str(j - i) + prev[i] \n",
    "                    i = j\n",
    "            cur += str(len(prev) - i) + prev[i] \n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        num = 1\n",
    "        s = '1'\n",
    "        while num < n:\n",
    "            s_new = ''\n",
    "            p1 = 0\n",
    "            p2 = 1\n",
    "            while p1 < len(s):\n",
    "                val = s[p1]\n",
    "                while p2 < len(s) and val == s[p2]:\n",
    "                    p2 += 1\n",
    "                s_new += str(p2-p1) + val\n",
    "                p1 = p2\n",
    "                p2 += 1\n",
    "            num += 1\n",
    "            s = s_new[:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        s='1'\n",
    "        goal=''\n",
    "        v=''\n",
    "        cnt=1\n",
    "        if(n==1):\n",
    "            return '1'\n",
    "        for i in range(1,n):\n",
    "            print('--------',i,goal)\n",
    "            goal=''\n",
    "            cnt=1\n",
    "            #1211\n",
    "            for i in range(len(s)):            \n",
    "                if(i+1==len(s)):\n",
    "                    goal=goal+str(cnt)+s[i]\n",
    "                    break;\n",
    "                print(i,i+1,s[i],s[i+1],cnt)\n",
    "                if(s[i]==s[i+1]):\n",
    "                    cnt+=1\n",
    "                else:\n",
    "                    goal=goal+str(cnt)+s[i]\n",
    "                    cnt=1\n",
    "            print(goal)\n",
    "            s=goal            \n",
    "        return goal\n",
    "        \n",
    "        \n",
    "            \n",
    "                \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        st='1'\n",
    "        if n<=1:return st\n",
    "        \n",
    "        for c in range(1,n):\n",
    "            cnt=1\n",
    "            countlist=[]\n",
    "            numlist=[]\n",
    "            length=len(st)\n",
    "            for i in range(length):\n",
    "                if i==0:\n",
    "                    continue\n",
    "\n",
    "                if st[i]!=st[i-1]:\n",
    "                    countlist.append(str(cnt))\n",
    "                    numlist.append(st[i-1])\n",
    "                    cnt=1\n",
    "                else:cnt+=1\n",
    "            else:\n",
    "                countlist.append(str(cnt))\n",
    "                numlist.append(st[length-1])\n",
    "\n",
    "            st=''\n",
    "            for i,j in zip(countlist,numlist):\n",
    "                st+=(i+j)\n",
    "            \n",
    "        return st\n",
    "            \n",
    "        \n",
    "            \n",
    "        \n",
    "                \n",
    "                \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        string = \"1\"\n",
    "        if n == 0:\n",
    "            return \"1\"\n",
    "        for i in range(2, n+1):\n",
    "            output = \"\"\n",
    "            while string:\n",
    "                # print(string)\n",
    "                index, firstNum = self.findDuplicate(string)\n",
    "                output += str(index)\n",
    "                output += firstNum\n",
    "                string = string[index:]\n",
    "            string = output\n",
    "        return string\n",
    "                    \n",
    "    def findDuplicate(self, string):\n",
    "        firstNum = string[0]\n",
    "        for i in range(len(string)):\n",
    "            print(string[0])\n",
    "            if string[i] != firstNum:\n",
    "                return i, firstNum\n",
    "        return len(string), firstNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = '1'\n",
    "        while n-1:\n",
    "            res = self.nextt(res)\n",
    "            n -= 1\n",
    "        return res\n",
    "        \n",
    "    def nextt(self,x):\n",
    "        count,idx,length,temp,res = 1,1,len(x),x[0],''\n",
    "        while idx < length:\n",
    "            if temp is x[idx]:\n",
    "                count += 1\n",
    "            else:\n",
    "                res += str(count)+temp\n",
    "                count,temp = 1,x[idx]\n",
    "            idx += 1\n",
    "        res += str(count)+temp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        # dic = {'one': '1', 'two': '2', 'three': '3', 'four': '4', 'five': '5', 'six': '6', 'seven': '7', 'eight': '8', 'nine': '9'}\n",
    "        # strs = ['1']\n",
    "        # strs[0] = '1'\n",
    "        # i = 0\n",
    "        # j = 1\n",
    "        # t = 0\n",
    "        # for k in range(1,31):\n",
    "        #     for i in range(0,len(strs[k-1])-1):\n",
    "        #         if strs[k-1][i] == strs[k-1][i+1]:\n",
    "        #             j += 1\n",
    "        #         else:\n",
    "        #             new_strs[t] = j\n",
    "        #             new_strs[t+1] = strs[k-1][i]\n",
    "        #             t += 2\n",
    "        #             j = 1\n",
    "        #             strs.append(new_strs)\n",
    "        # return strs[n-1]\n",
    "        # d = {'1': '1'}\n",
    "        # d = ['1', '123','11254']\n",
    "        d = ['1',]\n",
    "        # if n == 1:\n",
    "        #     return 1\n",
    "        if n < 1:\n",
    "            return False\n",
    "        # k = 1\n",
    "        for k in range(1,31):\n",
    "            if k <= len(d):\n",
    "                s = d[k-1] + '0'\n",
    "                # print(s)\n",
    "                # print(type(s))\n",
    "                # print(s.join('0'))\n",
    "                # s.append(0)\n",
    "                j = 1\n",
    "                # t = 0\n",
    "                new = ''\n",
    "                for i in range(0, len(s)-1):\n",
    "                    if s[i] == s[i+1]:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        new = new + str(j) +s[i]\n",
    "\n",
    "                        # new.insert(-1,j)\n",
    "                        # new.insert(-1,s[i])\n",
    "                        # t += 2\n",
    "                        j = 1\n",
    "                d.append(new)\n",
    "        return d[n-1]\n",
    "# ss = Solution()\n",
    "# print(ss.countAndSay(5))\n",
    "                        \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: 'int') -> 'str':\n",
    "        def count(tempstrr):\n",
    "            restemp=\"\"\n",
    "            temp=\"0\"\n",
    "            t=0\n",
    "            for i in tempstrr:\n",
    "                if i==temp:\n",
    "                    t+=1\n",
    "                else:\n",
    "                    if temp!=\"0\":\n",
    "                        restemp+=str(t)\n",
    "                        restemp+=temp\n",
    "                    t=1\n",
    "                    temp=i\n",
    "            return restemp+str(t)+temp\n",
    "        res=\"1\"\n",
    "        for i in range(1,n):\n",
    "            res=count(res)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        if n==1:\n",
    "            return '1'\n",
    "        elif n==2:\n",
    "            return '11'\n",
    "        x=self.countAndSay(n-1)\n",
    "        y=''\n",
    "        count=1\n",
    "        for i in range(len(x)):\n",
    "             \n",
    "            if i<len(x)-1 and x[i+1]==x[i]:\n",
    "                count+=1\n",
    "            else:\n",
    "                y+=str(count)\n",
    "                y+=str(x[i])\n",
    "                count=1\n",
    "        return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        if n < 1 or n > 30:\n",
    "            print(\"输入不符合要求\")\n",
    "        item_list = [\"1\"]\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            num = item_list[i][0]\n",
    "            count = 0\n",
    "            str_next = \"\"\n",
    "            for j in range(len(item_list[i])):\n",
    "                if item_list[i][j] == num:\n",
    "                    count += 1\n",
    "                    num = item_list[i][j]\n",
    "                else:\n",
    "                    str_next = str_next + str(count) + str(num)\n",
    "                    num = item_list[i][j]\n",
    "                    count = 1\n",
    "            str_next = str_next + str(count) + str(num)\n",
    "            item_list.append(str_next)\n",
    "            i += 1\n",
    "        return item_list[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        num = []\n",
    "        num.append(\"\")\n",
    "        num.append(\"1\")\n",
    "        if n==1: return num[1]\n",
    "        for i in range(2,n+1):\n",
    "            p = []\n",
    "            s = \"\"\n",
    "            for x in num[i-1]:\n",
    "                if p==[] or x==p[0]:\n",
    "                    p.append(x)\n",
    "                else:\n",
    "                    s += str(len(p))\n",
    "                    s += p[0]\n",
    "                    p = []\n",
    "                    p.append(x)\n",
    "            s += str(len(p))\n",
    "            s += p[0]\n",
    "            num.append(s)\n",
    "        \n",
    "        return num[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        \n",
    "        temp=\"1\"\n",
    "        for i in range(n-1):\n",
    "            newtemp=''\n",
    "            j=0\n",
    "            while j < (len(temp)):\n",
    "                count=1\n",
    "                while j < len(temp)-1 and temp[j]==temp[j+1]:\n",
    "                    count+=1\n",
    "                    j+=1\n",
    "                newtemp+=str(count)+temp[j]\n",
    "                j+=1\n",
    "            temp=newtemp\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cas = ['', '1', '11']\n",
    "        last = '11'\n",
    "        for x in range(3, 31):\n",
    "            i, n = 1, len(last)\n",
    "            accumulated = 1\n",
    "            result = ''\n",
    "            while i < n:\n",
    "                if last[i] == last[i - 1]:\n",
    "                    accumulated += 1\n",
    "                else:\n",
    "                    result += (str(accumulated) + last[i - 1])\n",
    "                    accumulated = 1\n",
    "                i += 1\n",
    "            if accumulated == 1:\n",
    "                result += ('1' + last[n - 1])\n",
    "            else:\n",
    "                result += (str(accumulated) + last[n - 1])\n",
    "            last = result\n",
    "            self.cas.append(result)\n",
    "\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        return self.cas[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        if n == 2:\n",
    "            return \"11\"\n",
    "        ss = [\"1\",\"11\"]\n",
    "        for i in range(1,n-1):\n",
    "            tmp = self.getCountString(ss[i])\n",
    "            ss.append(tmp)\n",
    "        return ss[-1]\n",
    "    \n",
    "    def getCountString(self,s:str) -> str:\n",
    "        cc = 0\n",
    "        start = 0\n",
    "        end = 0\n",
    "        re = \"\"\n",
    "        while end < len(s):\n",
    "            if s[start] == s[end]:\n",
    "                cc += 1\n",
    "                end += 1\n",
    "            else:\n",
    "                re += str(cc)\n",
    "                re += s[start]\n",
    "                \n",
    "                cc = 0\n",
    "                start = end\n",
    "        re += str(cc)\n",
    "        re += s[-1]\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        cur_str = '1'\n",
    "        for i in range(n-1):\n",
    "            cur_str = self.transform(cur_str)\n",
    "        return cur_str\n",
    "\n",
    "    def transform(self, s):\n",
    "        cur_digit = ''\n",
    "        cnt = 0\n",
    "        transStr = ''\n",
    "        for i in range(len(s)):\n",
    "            if cur_digit != s[i]:\n",
    "                if cnt != 0:\n",
    "                    transStr = transStr + str(cnt)\n",
    "                    transStr = transStr + cur_digit\n",
    "                cur_digit = s[i]\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if i == len(s) - 1:\n",
    "                transStr = transStr + str(cnt)\n",
    "                transStr = transStr + cur_digit\n",
    "                return transStr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        \n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "\n",
    "        pre = ''\n",
    "        cur = '1'\n",
    "        \n",
    "        for _ in range(1, n):\n",
    "            pre = cur # 上一个\n",
    "            cur = ''\n",
    "            # 快慢指针\n",
    "            slow = fast = 0\n",
    "            while slow < len(pre): # 遍历完上一个句子\n",
    "                while fast<len(pre) and pre[fast]==pre[slow]:\n",
    "                    fast += 1\n",
    "                cur += str(fast-slow) + pre[slow]\n",
    "                slow = fast\n",
    "            print( cur )\n",
    "\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        if n==1:\n",
    "            return '1'\n",
    "        else:\n",
    "            input=self.countAndSay(n-1)\n",
    "            result=[]\n",
    "            m=1\n",
    "            for i in range(1,len(input)+1):\n",
    "                if i<len(input) and (input[i]==input[i-1]):\n",
    "                    m+=1\n",
    "                else:\n",
    "                    n=input[i-1]\n",
    "                    result.append(m)\n",
    "                    result.append(n)\n",
    "                    m=1\n",
    "        return \"\".join([str(num) for num in result])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        s = self.countAndSay(n - 1)\n",
    "        idx, n, res =  0, len(s), []\n",
    "        while idx < n:\n",
    "            cnt = 1\n",
    "            while idx < n - 1 and s[idx] == s[idx+1]:\n",
    "                cnt += 1\n",
    "                idx += 1\n",
    "            res.append(str(cnt))\n",
    "            res.append(s[idx])\n",
    "            idx += 1\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        def helper(answer, n):\n",
    "            if n - 1 == 0:\n",
    "                return answer\n",
    "            else:\n",
    "                result = [str(len(item[0]))+item[1] for item in re.findall(r'((\\d)\\2*)', answer)] \n",
    "                \n",
    "                \n",
    "                # (\\d) 组号是2，匹配的结果比如\"111\",(\"111\",\"1\"), \n",
    "                # r'((\\d)\\2*)'有两个分组，第一个分组匹配最外层括号，第二个分组匹配\\d\n",
    "                return helper(\"\".join(result), n-1)\n",
    "        \n",
    "        return helper(\"1\", n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        pre = ''\n",
    "        cur = '1'\n",
    "        for _ in range(1, n):\n",
    "            pre = cur\n",
    "            cur = ''\n",
    "            start = 0\n",
    "            end = 0\n",
    "            while end < len(pre):\n",
    "                while end < len(pre) and pre[start] == pre[end]:\n",
    "                    end += 1\n",
    "                cur += str(end-start) + pre[start]\n",
    "                start = end\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        dp = [0]*n\n",
    "        dp[0] = \"1\"\n",
    "        for i in range(1, n):\n",
    "            dp[i] = self.getCount(dp[i-1])\n",
    "        return dp[-1]\n",
    "    \n",
    "    def getCount(self, num_str):\n",
    "        cur = \"\"\n",
    "        cnt = 0\n",
    "        res = \"\"\n",
    "        for char in num_str:\n",
    "            if char == cur:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if cnt != 0 and cur:\n",
    "                    res += str(cnt)+cur\n",
    "                cur = char\n",
    "                cnt = 1\n",
    "        if cnt != 0 and cur:\n",
    "            res += str(cnt)+cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def countAndSay(self, n: int) -> str:\n",
    "    def countAndSay(self,n):\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        \n",
    "        prev = self.countAndSay(n - 1)\n",
    "        result = \"\"\n",
    "        count = 1\n",
    "        for i in range(1, len(prev)):\n",
    "            if prev[i] == prev[i - 1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                result += str(count) + prev[i - 1]\n",
    "                count = 1\n",
    "        result += str(count) + prev[-1]\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                tem = \"1\"\n",
    "            else:\n",
    "                # print(tem)\n",
    "                tem = self.cou(tem)\n",
    "\n",
    "        # tem = self.cou('55443322221')\n",
    "        return tem\n",
    "         \n",
    "\n",
    "    def cou(self, s: str) -> str:\n",
    "\n",
    "        res = str()\n",
    "        # print(s, len(s))\n",
    "        com = s[0]\n",
    "        count = 1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == com:\n",
    "                count += 1\n",
    "            else:\n",
    "                res = res + str(count) + com\n",
    "                com = s[i]\n",
    "                count = 1\n",
    "        res = res + str(count) + com\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        def say(k):\n",
    "            if k == 1:\n",
    "                temp = \"1\"\n",
    "                return temp\n",
    "            else:\n",
    "                temp = say(k-1)\n",
    "            point = -1\n",
    "            nowcollect = -1\n",
    "            se = []\n",
    "            for i in range(len(temp)):\n",
    "                if nowcollect != int(temp[i]):\n",
    "                    point += 1\n",
    "                    nowcollect = int(temp[i])\n",
    "                    se.append([1,int(temp[i])])\n",
    "                else:\n",
    "                    se[point][0]+=1\n",
    "            res = \"\"\n",
    "            for x,y in se:\n",
    "                res += str(x) + str(y)\n",
    "            return res\n",
    "\n",
    "        return say(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "\n",
    "        # 转为字符串\n",
    "        s = \"1\"\n",
    "        step = 1\n",
    "\n",
    "        while step < n:\n",
    "            # 分割字符串，连续相同的字符串，划分到同一个部分\n",
    "            l=[[s[0],1]]\n",
    "            for i in range(1,len(s)):\n",
    "                if s[i] == s[i-1]:\n",
    "                    l[-1][1]+=1\n",
    "                else:\n",
    "                    l.append([s[i],1])\n",
    "            # print(l)\n",
    "            # 根据字符串的字符和数量，转化为新的字符串\n",
    "            s = ''.join([str(j)+i for i,j in l])\n",
    "            # print(s)\n",
    "            # 递归进入下一个循环\n",
    "            step+=1\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        prev = \"1\"\n",
    "        for i in range(n-1):\n",
    "            curr = \"\"\n",
    "            pos = 0\n",
    "            start = 0\n",
    "\n",
    "            while pos < len(prev):\n",
    "                while pos < len(prev) and prev[pos] == prev[start]:\n",
    "                    pos += 1\n",
    "                curr += str(pos - start) + prev[start]\n",
    "                start = pos\n",
    "            prev = curr\n",
    "        \n",
    "        return prev\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        ans = '1#'\n",
    "        for i in range(1, n):\n",
    "            t, cnt = '', 1\n",
    "            for j in range(1, len(ans)):\n",
    "                if ans[j] == ans[j - 1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    t += (str(cnt) + ans[j - 1])\n",
    "                    cnt = 1\n",
    "            t += '#'\n",
    "            ans = t\n",
    "        return ans[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        def say(ist):\n",
    "            if not ist: return ist\n",
    "            pv, pc = f'{ist[0]}', 1\n",
    "            res = ''\n",
    "            for x in ist[1:]:\n",
    "                if x == pv:\n",
    "                    pc +=1\n",
    "                else:\n",
    "                    res += f'{pc}{pv}'\n",
    "                    pv = x\n",
    "                    pc = 1\n",
    "            res += f'{pc}{pv}'\n",
    "            return res\n",
    "\n",
    "        if n == 1: return '1'\n",
    "        res = '1'\n",
    "        for i in range(2, n+1):\n",
    "            res = say(res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countAndSay(self, n: int) -> str:\n",
    "        s=\"1\"\n",
    "        for i in range(1,n):\n",
    "            l=1\n",
    "            tmp=\"\"\n",
    "            for j in range(1,len(s)):\n",
    "                if s[j]==s[j-1]:\n",
    "                    l+=1\n",
    "                else:\n",
    "                    tmp+=str(l)\n",
    "                    tmp+=s[j-1]\n",
    "                    l=1\n",
    "            tmp+=str(l)\n",
    "            tmp+=s[len(s)-1]\n",
    "            s=tmp\n",
    "        return s"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
